home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / answers / rec / puzzles / archive / competition / part3 < prev    next >
Encoding:
Text File  |  1993-08-18  |  55.9 KB  |  1,484 lines
  1. Newsgroups: rec.puzzles,news.answers,rec.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech!europa.eng.gtefsd.com!uunet!questrel!chris
  3. From: chris@questrel.com (Chris Cole)
  4. Subject: rec.puzzles Archive (competition), part 08 of 35
  5. Message-ID: <puzzles/archive/competition/part3_745653851@questrel.com>
  6. Followup-To: rec.puzzles
  7. Summary: This is part of an archive of questions
  8.  and answers that may be of interest to
  9.  puzzle enthusiasts.
  10.  Part 1 contains the index to the archive.
  11.  Read the rec.puzzles FAQ for more information.
  12. Sender: chris@questrel.com (Chris Cole)
  13. Reply-To: archive-comment@questrel.com
  14. Organization: Questrel, Inc.
  15. References: <puzzles/archive/Instructions_745653851@questrel.com>
  16. Date: Wed, 18 Aug 1993 06:04:51 GMT
  17. Approved: news-answers-request@MIT.Edu
  18. Expires: Thu, 1 Sep 1994 06:04:11 GMT
  19. Lines: 1462
  20. Xref: senator-bedfellow.mit.edu rec.puzzles:25012 news.answers:11532 rec.answers:1932
  21.  
  22. Archive-name: puzzles/archive/competition/part3
  23. Last-modified: 17 Aug 1993
  24. Version: 4
  25.  
  26.  
  27. ==> competition/games/rubiks/rubiks.cube.p <==
  28. What is known about bounds on solving Rubik's cube?
  29.  
  30. ==> competition/games/rubiks/rubiks.cube.s <==
  31. The "official" world record was set by Minh Thai at the 1982 World
  32. Championships in Budapest Hungary, with a time of 22.95 seconds.
  33.  
  34. Keep in mind mathematicians provided standardized dislocation patterns
  35. for the cubes to be randomized as much as possible.
  36.  
  37. The fastest cube solvers from 19 different countries had 3 attempts each
  38. to solve the cube as quickly as possible.   Minh and several others have
  39. unofficially solved the cube in times between 16 and 19 seconds.
  40. However, Minh averages around 25 to 26 seconds after 10 trials, and my
  41. best average of ten trials is about 27 seconds (although it is usually
  42. higher).
  43.  
  44. Consider that in the World Championships 19 of the world's fastest cube
  45. solvers each solved the cube 3 times and no one solved the cube in less
  46. than 20 seconds...
  47.  
  48. God's algorithm is the name given to an as yet (as far as I know)
  49. undiscovered method to solve the rubik's cube in the least number of
  50. moves; as opposed to using 'canned' moves.
  51.  
  52. The known lower bound is 18 moves. This is established by looking at
  53. things backwards: suppose we can solve a position in N moves. Then by
  54. running the solution backwards, we can also go from the solved position
  55. to the position we started with in N moves. Now we count how many
  56. sequences of N moves there are from the starting position, making
  57. certain that we don't turn the same face twice in a row:
  58.  
  59.   N=0: 1 (empty) sequence;
  60.   N=1: 18 sequences (6 faces can be turned, each in 3 different ways)
  61.   N=2: 18*15 sequences (take any sequence of length 1, then turn any of the
  62.        five faces which is not the last face turned, in any of 3
  63.        different ways); N=3: 18*15*15 sequences (take any sequence of
  64.        length 2, then turn any of the five faces which is not the last
  65.        face turned, in any of 3 different ways); :  :  N=i: 18*15^(i-1)
  66.        sequences.
  67.  
  68. So there are only 1 + 18 + 18*15 + 18*15^2 + ... + 18*15^(n-1)
  69. sequences of moves of length n or less. This sequence sums to
  70. (18/14)*(15^n - 1) + 1.  Trying particular values of n, we find that
  71. there are about 8.4 * 10^18 sequences of length 16 or less, and about
  72. 1.3 times 10^20 sequences of length 17 or less.
  73.  
  74. Since there are 2^10 * 3^7 * 8! * 12!, or about 4.3 * 10^19, possible
  75. positions of the cube, we see that there simply aren't enough sequences
  76. of length 16 or less to reach every position from the starting
  77. position. So not every position can be solved in 16 or less moves -
  78. i.e. some positions require at least 17 moves.
  79.  
  80. This can be improved to 18 moves by being a bit more careful about
  81. counting sequences which produce the same position. To do this, note
  82. that if you turn one face and then turn the opposite face, you get
  83. exactly the same result as if you'd done the two moves in the opposite
  84. order. When counting the number of essentially different sequences of N
  85. moves, therefore, we can split into two cases:
  86.  
  87. (a) Last two moves were not of opposite faces. All such sequences can be
  88.     obtained by taking a sequence of length N-1, choosing one of the 4 faces
  89.     which is neither the face which was last turned nor the face opposite
  90.     it, and choosing one of 3 possible ways to turn it. (If N=1, so that the
  91.     sequence of length N-1 is empty and doesn't have a last move, we
  92.     can choose any of the 6 faces.)
  93.  
  94. (b) Last two moves were of opposite faces. All such sequences can be
  95.     obtained by taking a sequence of length N-2, choosing one of the 2
  96.     opposite face pairs that doesn't include the last face turned, and
  97.     turning each of the two faces in this pair (3*3 possibilities for how it
  98.     was turned). (If N=2, so that the sequence of length N-2 is empty and
  99.     doesn't have a last move, we can choose any of the 3 opposite face
  100.     pairs.)
  101.  
  102. This gives us a recurrence relation for the number X_N of sequences of
  103. length N:
  104.  
  105.   N=0: X_0                               = 1 (the empty sequence)
  106.   N=1: X_1 = 18 * X_0                    = 18
  107.   N=2: X_2 = 12 * X_1     + 27 * X_0     = 243
  108.   N=3: X_3 = 12 * X_2     + 18 * X_1     = 3240
  109.   :
  110.   :
  111.   N=i: X_i = 12 * X_(i-1) + 18 * X_(i-2)
  112.  
  113. If you do the calculations, you find that X_0 + X_1 + X_2 + ... + X_17 is
  114. about 2.0 * 10^19. So there are fewer essentially different sequences of
  115. moves of length 17 or less than there are positions of the cube, and so some
  116. positions require at least 18 moves.
  117.  
  118. The upper bound of 50 moves is I believe due to Morwen Thistlethwaite, who
  119. developed a technique to solve the cube in a maximum of 50 moves. It
  120. involved a descent through a chain of subgroups of the full cube group,
  121. starting with the full cube group and ending with the trivial subgroup
  122. (i.e.  the one containing the solved position only). Each stage involves a
  123. careful examination of the cube, essentially to work out which coset of the
  124. target subgroup it is in, followed by a table look-up to find a sequence to put
  125. it into that subgroup. Needless to say, it was not a fast technique!
  126.  
  127. But it was fascinating to watch, because for the first three quarters or
  128. so of the solution, you couldn't really see anything happening - i.e. the
  129. position continued to appear random! If I remember correctly, one of the
  130. final subgroups in the chain was the subgroup generated by all the double
  131. twists of the faces - so near the end of the solution, you would suddenly
  132. notice that each face only had two colours on it. A few moves more and the
  133. solution was complete. Completely different from most cube solutions, in
  134. which you gradually see order return to chaos: with Morwen's solution, the
  135. order only re-appeared in the last 10-15 moves.
  136.  
  137. * Mark's Update/Comments ----------------------------------------------
  138.  
  139. * Despite some accounts of Thistlethwaite's method, it is possible to
  140. * follow the progression of his algorithm. Clearly after Stage 2 is
  141. * completed the L and R faces will have L and R colours on them only.
  142. * After Stage 3 is complete the characteristics of the square's group
  143. * is clearly visible on all 6 sides. It is harder to understand what
  144. * is accomplished in Stage 1.
  145. *
  146. * ---------------------------------------------------------------------
  147.  
  148. With God's algorithm, of course, I would expect this effect to be even more
  149. pronounced: someone solving the cube with God's algorithm would probably
  150. look very much like a film of someone scrambling the cube, run in
  151. reverse!
  152.  
  153. Finally, something I'd be curious to know in this context: consider the
  154. position in which every cubelet is in the right position, all the corner
  155. cubelets are in the correct orientation, and all the edge cubelets are
  156. "flipped" (i.e. the only change from the solved position is that every edge
  157. is flipped). What is the shortest sequence of moves known to get the cube
  158. into this position, or equivalently to solve it from this position? (I know
  159. of several sequences of 24 moves that do the trick.)
  160.  
  161. * Mark's Update/Comments ----------------------------------------------
  162. *
  163. *  This is from my file cmoves.txt which includes the best known
  164. *   sequences for interesting patterns:
  165. *
  166. * p3  12 flip    R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3  (20)
  167. *                   R2 U3 F2 D3
  168. *
  169. * ---------------------------------------------------------------------
  170.  
  171. The reason I'm interested in this particular position: it is the unique
  172. element of the centre of the cube group. As a consequence, I vaguely suspect
  173. (I'd hardly like to call it a conjecture :-) it may lie "opposite" the
  174. solved position in the cube graph - i.e. the graph with a vertex for each
  175. position of the cube and edges connecting positions that can be transformed
  176. into each other with a single move. If this is the case, then it is a good
  177. candidate to require the maximum possible number of moves in God's
  178. algorithm.
  179.  
  180.     -- David Seal dseal@armltd.co.uk
  181.  
  182. To my knowledge, no one has ever demonstrated a specific cube position
  183. that takes 15 moves to solve.  Furthermore, the lower bound is known to
  184. be greater than 15, due to a simple proof.
  185.  
  186. * ---------------------------------------------------------------------
  187. * Mark>  Definitely sequences exist in the square's group of length 15
  188. *     >  e.g. Antipode 2   R2 B2 D2 F2 D2 F2 T2 L2 T2 D2 F2 T2 L2 T2 B2
  189. * ---------------------------------------------------------------------
  190.  
  191. The way we know the lower bound is by working backwards counting how
  192. many positions we can reach in a small number of moves from the solved
  193. position.  If this is less than 43,252,003,274,489,856,000 (the total
  194. number of positions of Rubik's cube) then you need more than that
  195. number of moves to reach the other positions of the cube.  Therefore,
  196. those positions will require more moves to solve.
  197.  
  198. The answer depends on what we consider a move.  There are three common
  199. definitions.  The most restrictive is the QF metric, in which only a
  200. quarter-turn of a face is allowed as a single move.  More common is
  201. the HF metric, in which a half-turn of a face is also counted as a
  202. single move.  The most generous is the HS metric, in which a quarter-
  203. turn or half-turn of a central slice is also counted as a single move.
  204. These metrics are sometimes called the 12-generator, 18-generator, and
  205. 27-generator metrics, respectively, for the number of primitive moves.
  206. The definition does not affect which positions you can get to, or even
  207. how you get there, only how many moves we count for it.
  208.  
  209. The answer is that even in the HS metric, the lower bound is 16,
  210. because at most 17,508,850,688,971,332,784 positions can be reached
  211. within 15 HS moves.  In the HF metric, the lower bound is 18, because
  212. at most 19,973,266,111,335,481,264 positions can be reached within 17
  213. HF moves.  And in the QT metric, the lower bound is 21, because at
  214. most 39,812,499,178,877,773,072 positions can be reached within 20 QT
  215. moves.
  216.  
  217.  -- jjfink@skcla.monsanto.com writes:
  218.  
  219.  
  220. Lately in this conference I've noted several messages related to Rubik's
  221. Cube and Square 1. I've been an avid cube fanatic since 1981 and I've
  222. been gathering cube information since.
  223.  
  224. Around Feb. 1990 I started to produce the Domain of the Cube Newsletter,
  225. which focuses on Rubik's Cube and all the cube variants produced to
  226. date. I include notes on unproduced prototype cubes which don't even
  227. exist, patent information, cube history (and prehistory), computer
  228. simulations of puzzles, etc. I'm up to the 4th issue.
  229.  
  230. Anyways, if you're interested in other puzzles of the scramble by
  231. rotation type you may be interested in DOTC. It's available free to
  232. anyone interested. I am especially interested in contributing articles
  233. for the newsletter, e.g. ideas for new variants, God's Algorithm.
  234.  
  235. Anyone ever write a Magic Dodecahedron simulation for a computer?
  236.  
  237. Drop me a SASE (say empire size) if you're interested in DOTC or if you
  238. would like to exchange notes on Rubik's Cube, Square 1 etc.
  239.  
  240. I'm also interested in exchanging puzzle simulations, e.g. Rubik's Cube,
  241. Twisty Torus, NxNxN Simulations, etc, for Amiga and IBM computers. I've
  242. written several Rubik's Cube solving programs, and I'm trying to make
  243. the definitive puzzle solving engine. I'm also interested in AI programs
  244. for Rubik's Cube and the like.
  245.  
  246. Ideal Toy put out the Rubik's Cube Newsletter, starting with
  247. issue #1 on May 1982. There were 4 issues in all.
  248.  
  249. They are:  #1, May    1982
  250.            #2, Aug    1982
  251.            #3, Winter 1983
  252.            #4, Aug    1983
  253.  
  254. There was another sort of magazine, published in several languages
  255. called Rubik's Logic and Fantasy in space. I believe there were 8
  256. issues in all. Unfortunately I don't have any of these! I'm willing
  257. to buy these off anyone interesting in selling. I would like to get the
  258. originals if at all possible...
  259.  
  260. I'm also interested in buying any books on the cube or related puzzles.
  261. In particular I am _very_ interested in obtaining the following:
  262.  
  263. Cube Games                               Don Taylor, Leanne Rylands
  264. Official Solution to Alexander's Star    Adam Alexander
  265. The Amazing Pyraminx                     Dr. Ronald Turner-Smith
  266. The Winning Solution                     Minh Thai
  267. The Winning Solution to Rubik's Revenge  Minh Thai
  268. Simple Solutions to Cubic Puzzles        James G. Nourse
  269.  
  270. I'm also interested in buying puzzles of the mechanical type.
  271. I'm still missing the Pyraminx Star (basically a Pyraminx with more tips
  272. on it), Pyraminx Ball, and the Puck.
  273.  
  274. If anyone out here is a fellow collector I'd like to hear from you.
  275. If you have a cube variant which you think is rare, or an idea for a
  276. cube variant we could swap notes.
  277.  
  278. I'm in the middle of compiling an exhaustive library for computer
  279. simulations of puzzles. This includes simulations of all Uwe Meffert's
  280. puzzles which he prototyped but _never_ produced. In fact, I'm in the
  281. middle of working on a Pyraminx Hexagon solver. What? Never heard of it?
  282. Meffert did a lot of other puzzles which never were made.
  283.  
  284. I invented some new "scramble by rotation" puzzles myself. My favourite
  285. creation is the Twisty Torus. It is a torus puzzle with segments (which
  286. slide around 360 degrees) with multiple rings around the circumference.
  287.  
  288. The computer puzzle simulation library I'm forming will be described
  289. in depth in DOTC #4 (The Domain of the Cube Newsletter). So if you
  290. have any interesting computer puzzle programs please email me and
  291. tell me all about them!
  292.  
  293. Also to the people interested in obtaining a subscription to DOTC,
  294. who are outside of Canada (which it seems is just about all of you!)
  295. please don't send U.S. or non-Canadian stamps (yeah, I know I said
  296. Self-Addressed Stamped Envelope before). Instead send me an
  297. international money order in Canadian funds for $6. I'll send you
  298. the first 4 issues (issue #4 is almost finished).
  299.  
  300. Mark Longridge
  301. Address: 259 Thornton Rd N, Oshawa Ontario Canada, L1J 6T2
  302. Email:   mark.longridge@canrem.com
  303.  
  304. One other thing, the six bucks is not for me to make any money. This
  305. is only to cover the cost of producing it and mailing it. I'm
  306. just trying to spread the word about DOTC and to encourage other
  307. mechanical puzzle lovers to share their ideas, books, programs and
  308. puzzles. Most of the programs I've written and/or collected are
  309. shareware for C64, Amiga and IBM. I have source for all my programs
  310. (all in C or Basic) and I am thinking of providing a disk with the
  311. 4th issue of DOTC. If the response is favourable I will continue
  312. to provide disks with DOTC.
  313.  
  314.     -- Mark Longridge <mark.longridge@canrem.com> writes:
  315.  
  316. It may interest people to know that in the latest issue of "Cubism For Fun" %
  317. (# 28 that I just received yesterday) there is an article by Herbert Kociemba
  318. from Darmstadt.  He describes a program that solves the cube.  He states that
  319. until now he has found no configuration that required more than 21 turns to
  320. solve.
  321.  
  322. He gives a 20 move manoeuvre to get at the "all edges flipped/
  323. all corners twisted" position:
  324.         DF^2U'B^2R^2B^2R^2LB'D'FD^2FB^2UF'RLU^2F'
  325. or in Varga's parlance:
  326.         dofitabiribirilobadafodifobitofarolotifa
  327.  
  328. Other things #28 contains are an analysis of Square 1, an article about
  329. triangular tilings by Martin Gardner, and a number of articles about other
  330. puzzles.
  331. --
  332. %  CFF is a newsletter published by the Dutch Cubusts Club NKC.
  333. Secretary:
  334.         Anneke Treep
  335.         Postbus 8295
  336.         6710 AG  Ede
  337.         The Netherlands
  338. Membership fee for 1992 is DFL 20 (about$ 11).
  339. --
  340.     -- dik t. winter <dik@cwi.nl>
  341.  
  342. References:
  343.  
  344. Mathematical Papers
  345. -------------------
  346.  
  347. Rubik's Revenge: The Group Theoretical Solution
  348. Mogens Esrom Larsen   A.M.M. Vol. 92 No. 6, June-July 1985, pages
  349. 381-390
  350.  
  351. Rubik's Groups
  352. E. C. Turner & K. F. Gold, American Mathematical Monthly,
  353. vol. 92 No. 9 November 1985, pp. 617-629.
  354.  
  355. Cubelike Puzzles - What Are They and How Do You Solve Them?
  356. J.A. Eidswick   A.M.M. Vol. 93 No. 3 March 1986, pp 157-176
  357.  
  358. The Slice Group in Rubik's Cube,  David Hecker, Ranan Banerji
  359. Mathematics Magazine, Vol. 58 No. 4 Sept 1985
  360.  
  361. The Group of the Hungarian Magic Cube
  362. Chris Rowley   Proceedings of the First Western Austrialian
  363.                 Conference on Algebra, 1982
  364.  
  365. Books
  366. -----
  367.  
  368. Rubik's Cubic Compendium
  369. Erno Rubik, Tamas Varga, et al, Edited by David Singmaster
  370. Oxford University Press, 1987
  371. Enslow Publishers Inc
  372.  
  373.  
  374.  
  375. ==> competition/games/rubiks/rubiks.magic.p <==
  376. How do you solve Rubik's Magic?
  377.  
  378. ==> competition/games/rubiks/rubiks.magic.s <==
  379. The solution is in a 3x3 grid with a corner missing.
  380.  
  381. +---+---+---+          +---+---+---+---+
  382. | 3 | 5 | 7 |          | 1 | 3 | 5 | 7 |
  383. +---+---+---+          +---+---+---+---+
  384. | 1 | 6 | 8 |          | 2 | 4 | 6 | 8 |
  385. +---+---+---+          +---+---+---+---+
  386. | 2 | 4 |              Original Shape
  387. +---+---+
  388.  
  389. To get the 2x4 "standard" shape into this shape, follow this:
  390. 1.  Lie it flat in front of you (4 going across).
  391. 2.  Flip the pair (1,2) up and over on top of (3,4).
  392. 3.  Flip the ONE square (2) up and over (1).
  393. [Note:  if step 3 won't go, start over, but flip the entire original shape
  394.         over (exposing the back).]
  395. 4.  Flip the pair (2,4) up and over on top of (5,6).
  396. 5.  Flip the pair (1,2) up and toward you on top of (blank,4).
  397. 6.  Flip the ONE square (2) up and left on top of (1).
  398. 7.  Flip the pair (2,4) up and toward you. 
  399.  
  400. Your puzzle won't be completely solved, but this is how to get the shape.
  401. Notice that 3,5,6,7,8 don't move.
  402.  
  403. ==> competition/games/scrabble.p <==
  404. What are some exceptional Scrabble Brand Crossword Game (TM) games?
  405.  
  406. ==> competition/games/scrabble.s <==
  407. The shortest Scrabble game:
  408.  
  409. The Scrabble Players News, Vol. XI No. 49, June 1983, contributed by
  410. Kyle Corbin of Raleigh, NC:
  411.  
  412.          [J]
  413.         J U S
  414.           S O X
  415.            [X]U
  416.  
  417. which can be done in 4 moves, JUS, SOX, [J]US, and [X]U.
  418.  
  419. In SPN Vol. XI, No. 52, December 1983, Alan Frank presented what
  420. he claimed is the shortest game where no blanks are used, also
  421. four moves:
  422.  
  423.                   C
  424.                  WUD
  425.                 CUKES
  426.              DEY
  427.               S
  428.  
  429. This was followed in SPN, Vol. XII No. 54, April 1984, by Terry Davis
  430. of Glasgow, KY:
  431.  
  432.               V
  433.                 V O[X]
  434.              [X]U,
  435.  
  436. which is three moves.  He noted that the use of two blanks prevents
  437. such plays as VOLVOX.  Unfortunately, it doesn't prevent SONOVOX.
  438.  
  439. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  440. Record for the highest Scrabble score in a single turn (in a legal position):
  441.  
  442. According to the Scrabble Players Newspaper (since renamed to 
  443. Scrabble Players News) issue 44, p13, the highest score for one
  444. turn yet discovered, using the Official Scrabble Players
  445. Dictionary, 1st ed. (the 2nd edition is now in use in club and
  446. tournament play) and the Websters 9th New Collegiate Dictionary,
  447. was the following:
  448.  
  449. d i s e q u i l i b r a t e D
  450. . . . . . . . e . . . . . . e
  451. . . . . . . . e . . . . . o m
  452. r a d i o a u t o g r a p(h)Y
  453. . . . . . . . . . . . w a s T
  454. . . . . . . . . . . b e . . h
  455. . . . . . . . . . . a . . g o
  456. . . . c o n j u n c t i v a L 
  457. . . . . . . . . . . . . . n o
  458. . . . . . . . f i n i k i n G
  459. . . . . . . . a . . . (l) e i
  460. . . . . . . . d . s p e l t Z
  461. . . . . . . w e . . . . . . e
  462. . . . . . . r . . . . . . o r
  463. m e t h o x y f l u r a n e S
  464.  
  465. for 1682 points.
  466.  
  467.  
  468. According to the May 1986 issue of GAMES, the highest known score achievable
  469. in one turn is 1,962 points.  The word is BENZOXYCAMPHORS formed across the
  470. three triple-word scores on the bottom of the board.  Apparently it was 
  471. discovered by Darryl Francis, Ron Jerome, and Jeff Grant.
  472.  
  473. As for other Scrabble trivia, the highest-scoring first move based on the
  474. Official Scrabble Players Dictionary is 120 points, with the words JUKEBOX,
  475. QUIZZED, SQUEEZE, or ZYMURGY.  If Funk & Wagnall's New Standard Dictionary
  476. is used then ZYXOMMA, worth 130 points, can be formed.
  477.  
  478. The highest-scoring game, based on Webster's Second and Third and on the
  479. Oxford English Dictionary, was devised by Ron Jerome and Ralph Beaman and
  480. totalled 4,142 points for the two players.  The highest-scoring words in
  481. the game were BENZOXYCAMPHORS, VELVETEEN, and JACKPUDDINGHOOD.
  482.  
  483. The following example of a SCRABBLE game produced a score of 2448 for one
  484. player and 1175 for the final word.  It is taken from _Beyond Language_ (1967)
  485. by Dmitri Borgman (pp. 217-218).  He credits this solution to Mrs. Josefa H.
  486. Byrne of San Francisco and implies that all words can be found in _Webster's
  487. Second Edition_.  The two large words (multiplied by 27 as they span 3 triple
  488. word scores) are ZOOPSYCHOLOGIST (a psychologist who treats animals rather
  489. than humans) and PREJUDICATENESS (the condition or state of being decided 
  490. beforehand).  The asterisks (*) represent the blank tiles. (Please excuse
  491. any typo's).
  492.  
  493.            Board                        Player1                 Player2
  494.  
  495. Z O O P S Y C H O L O G I S T    ABILITY             76   ERI, YE     9
  496. O N         H A   U     R O W    MAN, MI             10   EN          2
  497. *         R I B   R O V E   I    FEN, FUN            14   MANIA       7
  498. L           T I K E         G    TABU                12   RIB         6
  499. O             L                  NEXT                11   AM          4
  500. G             I                  AX                   9   END         6
  501. I             T                  IT, TIKE            10   LURE        6
  502. *             Y E                LEND, LOGIC*AL      79   OO*LOGICAL  8
  503. A               R                FUND, JUD           27   ATE, MA     7
  504. L E N D       M I                ROVE                14   LO          2
  505.     E         A             Q    DARE, DE            13   ES, ES, RE  6 
  506. W A X     F E N             U    RE, ROW             14   IRE, IS, SO 7
  507. E   T A B U   I             A    DARED, QUAD         22   ON          4
  508. E         N   A M   D A R E D    WAX, WEE            27   WIG         9
  509. P R E J U D I C A T E N E S S    CHIT, HA            14   ON          2
  510.                                  PREJUDICATENESS,
  511.                                    AN, MANIAC,
  512.                                    QUADS, WEEP      911   OOP         8
  513.                                  ZOOPSYCHOLOGIST,
  514.                                    HABILITY, TWIG,
  515.                                    ZOOLOGICAL      1175
  516.                                  --------------------------------------
  517.                                  Total:            2438              93
  518.  
  519.                                  F, N, V, T in 
  520.                                  loser's hand:      +10             -10
  521.                                  --------------------------------------
  522.                                  Final Score:      2448              83
  523.  
  524.  
  525. ---------------------------------------------------------------------------
  526. It is possible to form the following 14 7-letter OSPD words from the
  527. non-blank tiles:
  528.  
  529. HUMANLY
  530. FATUOUS
  531. AMAZING
  532. EERIEST
  533. ROOFING
  534. TOILERS
  535. QUIXOTE
  536. JEWELRY
  537. CAPABLE
  538. PREVIEW
  539. BIDDERS
  540. HACKING
  541. OVATION
  542. DONATED
  543.  
  544. ==> competition/games/set.p <==
  545. What is the size of the largest collection of cards from which NO "set"
  546. can be selected ?
  547.  
  548. ==> competition/games/set.s <==
  549. I can get 20:
  550.  
  551. 1ROL
  552. 1GDL
  553. 1GDM
  554. 1GOM
  555. 1GSL
  556. 1PDH
  557. 1PDM
  558. 1POL
  559. 1POM
  560. 2RSL
  561. 2PDM
  562. 3ROL
  563. 3ROM
  564. 3RSL
  565. 3RSH
  566. 3GDM
  567. 3GOL
  568. 3GSL
  569. 3GSM
  570. 3POM
  571.  
  572. This collection of 20 is a local maximum.
  573.  
  574. The small C progam shown below was used to check for all possible
  575. extensions to a collection of 21.
  576.  
  577. Of course this leaves open the question whether there exists a completely
  578. different collection of 21 from which no "set" can be selected.
  579.  
  580. -- Gene Miller
  581.  
  582. ------- C Program enclosed -------
  583. #define N 21
  584.  
  585. static int data[N][4]= {
  586.     1, 1, 2, 1, /* 00 */
  587.     1, 2, 1, 1, /* 01 */
  588.     1, 2, 1, 2, /* 02 */
  589.     1, 2, 2, 2, /* 03 */
  590.     1, 2, 3, 1, /* 04 */
  591.     1, 3, 1, 3, /* 05 */
  592.     1, 3, 1, 2, /* 06 */
  593.     1, 3, 2, 1, /* 07 */
  594.     1, 3, 2, 2, /* 08 */
  595.     2, 1, 3, 1, /* 09 */
  596.     2, 3, 1, 2, /* 10 */
  597.     3, 1, 2, 1, /* 11 */
  598.     3, 1, 2, 2, /* 12 */
  599.     3, 1, 3, 1, /* 13 */
  600.     3, 1, 3, 3, /* 14 */
  601.     3, 2, 1, 2, /* 15 */
  602.     3, 2, 2, 1, /* 16 */
  603.     3, 2, 3, 1, /* 17 */
  604.     3, 2, 3, 2, /* 18 */
  605.     3, 3, 2, 2, /* 19 */
  606.     0, 0, 0, 0  /* 20 */    /* leave space for Nth combo */
  607. };
  608.  
  609. main()
  610. {    
  611.     int x, y, z, w;
  612.  
  613.     for (x=1; x<=3; x++)    /* check all combos */
  614.     for (y=1; y<=3; y++)
  615.         for (z=1; z<=3; z++)
  616.         for (w=1; w<=3; w++)
  617.             printf ("%d %d %d %d -> sets=%d\n", x, y, z, w,
  618.             check (x, y, z, w));
  619. }
  620.  
  621. int check(x,y,z,w)
  622. int x, y, z, w;
  623. {
  624.     int i,j,k,m;
  625.     int errors, sets;
  626.  
  627.     for (i=0; i<N; i++)        /* check for pre-existing combos */
  628.     if (x==data[i][0] &&
  629.         y==data[i][1] &&
  630.         z==data[i][2] &&
  631.         w==data[i][3] ) {
  632.     return -1;        /* discard pre-existing*/
  633.     }
  634.  
  635.     data[N-1][0] = x;    /* make this the Nth combo */
  636.     data[N-1][1] = y;
  637.     data[N-1][2] = z;
  638.     data[N-1][3] = w;
  639.  
  640.     sets = 0;            /* start counting sets */
  641.     for (i=0; i<N; i++)        /* look for sets */
  642.     for (j=i+1; j<N; j++)
  643.         for (k=j+1; k<N; k++) {
  644.         errors = 0;
  645.         for (m=0; m<4; m++) {
  646.             if (data[i][m] == data[j][m]) {
  647.             if (data[k][m] != data[i][m]) errors++;
  648.             if (data[k][m] != data[j][m]) errors++;
  649.             }
  650.             else {
  651.             if (data[k][m] == data[i][m]) errors++;
  652.             if (data[k][m] == data[j][m]) errors++;
  653.             }
  654.         }
  655.         if (errors == 0)    /* no errors means is a set */
  656.             sets++; /* increment number of sets */
  657.         }
  658.     return sets;
  659. }
  660. -- 
  661.  
  662. I did some more experimenting. With the enclosed C program, I looked at many
  663. randomly generated collections. In an earlier version of this program I
  664. got one collection of 20 from a series of 100 trials. The rest were collections
  665. ranging in size from 16 to 19. Unfortunately, in an attempt to make this
  666. program more readable and more general, I changed the algorithm slightly and
  667. I haven't been able to achieve 20 since then. I can't remember enough about
  668. my changes to be able to get back to the previous version. In the most recent
  669. 1000 trials all of the maximaml collections range in size from 16 to 18.
  670.  
  671. I think that this experiment has shed very little light on what is the
  672. global maximum, since the search space is many orders of magnitude larger
  673. than what can be tried in a reasonable amount of time through random
  674. searching.
  675.  
  676. I assume that Mr. Ring found his collection of 20 by hand. This indicates
  677. that an intelligent search may be more fruitful than a purely random one.
  678.  
  679. ------------------ Program enclosed -------------
  680. int n;
  681. int data[81][4];
  682.  
  683. main()
  684. {
  685.     int i;
  686.  
  687.     for (i=0; i<1000; i++) {    /* Do 1000 independent trials */
  688.     printf ("Trial %d:\n", i);
  689.     try();
  690.     }
  691. }
  692.  
  693. try()
  694. {    
  695.     int i;
  696.     int x, y, z, w;
  697.  
  698.     n = 0;            /* set collection size to zero */
  699.     for (i=0; i<100; i++) {    /* try 100 random combos */
  700.     x = 1 + rand()%3;
  701.     y = 1 + rand()%3;
  702.     z = 1 + rand()%3;
  703.     w = 1 + rand()%3;
  704.     check (x, y, z, w);
  705.     }
  706.  
  707.     for (x=1; x<=3; x++)    /* check all combos */
  708.     for (y=1; y<=3; y++)
  709.         for (z=1; z<=3; z++)
  710.         for (w=1; w<=3; w++)
  711.             check (x, y, z, w);
  712.  
  713.     printf ("    collection size=%d\n", n);
  714. }
  715.  
  716. int check(x, y, z, w)    /* check whether a new combo can be added */
  717. int x, y, z, w;
  718. {
  719.     int i,j,k,m;
  720.     int errors, sets;
  721.  
  722.     for (i=0; i<n; i++)        /* check for pre-existing combos */
  723.     if (x==data[i][0] &&
  724.         y==data[i][1] &&
  725.         z==data[i][2] &&
  726.         w==data[i][3] ) {
  727.     return -1;        /* discard pre-existing*/
  728.     }
  729.  
  730.     data[n][0] = x;    /* make this the nth combo */
  731.     data[n][1] = y;
  732.     data[n][2] = z;
  733.     data[n][3] = w;
  734.  
  735.     sets = 0;            /* start counting sets */
  736.     for (i=0; i<=n; i++)        /* look for sets */
  737.     for (j=i+1; j<=n; j++)
  738.         for (k=j+1; k<=n; k++) {
  739.         errors = 0;
  740.         for (m=0; m<4; m++) {
  741.             if (data[i][m] == data[j][m]) {
  742.             if (data[k][m] != data[i][m]) errors++;
  743.             if (data[k][m] != data[j][m]) errors++;
  744.             }
  745.             else {
  746.             if (data[k][m] == data[i][m]) errors++;
  747.             if (data[k][m] == data[j][m]) errors++;
  748.             }
  749.         }
  750.         if (errors == 0)    /* no errors means is a set */
  751.             sets++; /* increment number of sets */
  752.         }
  753.     if (sets == 0) {
  754.     n++;        /* increment collection size */
  755.     printf ("%d %d %d %d\n", x, y, z, w);
  756.     }
  757.     return sets;
  758. }
  759. ------------------ end of enclosed program -------------
  760. -- Gene
  761. -- 
  762. Gene Miller            Multimedia Communications
  763. NYNEX Science & Technology    Phone:  914 644 2834
  764. 500 Westchester Avenue        Fax:    914 997 2997, 914 644 2260
  765. White Plains, NY 10604        Email:  gene@nynexst.com
  766.  
  767. ==> competition/games/soma.p <==
  768. What is the solution to Soma Cubes?
  769.  
  770. ==> competition/games/soma.s <==
  771. The soma cube is dissected in excruciating detail in volume 2 of
  772. "Winning Ways" by Conway, Berlekamp and Guy, in the same chapter as the
  773. excruciatingly detailed dissection of Rubik's Cube.
  774.  
  775. ==> competition/games/square-1.p <==
  776. Does anyone have any hints on how to solve the Square-1 puzzle?
  777.  
  778. ==> competition/games/square-1.s <==
  779.                 SHAPES
  780.  
  781. 1. There are 29 different shapes for a side, counting reflections:
  782.     1 with 6 corners, 0 edges
  783.     3 with 5 corners, 2 edges
  784.    10 with 4 corners, 4 edges
  785.    10 with 3 corners, 6 edges
  786.     5 with 2 corners, 8 edges
  787.  
  788. 2. Naturally, a surplus of corners on one side must be compensated
  789.    by a deficit of corners on the other side.  Thus there are 1*5 +
  790.    3*10 + C(10,2) = 5 + 30 + 55 = 90 distinct combinations of shapes,
  791.    not counting the middle layer.
  792.  
  793. 3. You can reach two squares from any other shape in at most 7 transforms,
  794.    where a transform consists of (1) optionally twisting the top, (2)
  795.    optionally twisting the bottom, and (3) flipping.
  796.  
  797. 4. Each transform toggles the middle layer between Square and Kite,
  798.    so you may need 8 transforms to reach a perfect cube.
  799.  
  800. 5. The shapes with 4 corners and 4 edges on each side fall into four
  801.    mutually separated classes.  Side shapes can be assigned values:
  802.    0: Square, Mushroom, and Shield; 1: Left Fist and Left Paw; 2:
  803.    Scallop, Kite, and Barrel; 3. Right Fist and Right Paw.  The top
  804.    and bottom's sum or difference, depending on how you look at them,
  805.    is a constant.  Notice that the side shapes with bilateral symmetry
  806.    are those with even values.
  807.  
  808. 6. To change this constant, and in particular to make it zero, you must
  809.    attain a position that does not have 4 corners and 4 edges on each
  810.    side.  Almost any such position will do, but returning to 4 corners
  811.    and 4 edges with the right constant is left to your ingenuity.
  812.  
  813. 7. If the top and bottom are Squares but the middle is a Kite, just flip
  814.    with the top and bottom 30deg out of phase and you will get a cube.
  815.  
  816.                 COLORS
  817.  
  818. 1. I do not know the most efficient way to restore the colors.  What
  819.    follows is my own suboptimal method.  All flips keep the yellow
  820.    stripe steady and flip the blue stripe.
  821.  
  822. 2. You can permute the corners without changing the edges, so first
  823.    get the edges right, then the corners.
  824.  
  825. 3. This transformation sends the right top edge to the bottom
  826.    and the left bottom edge to the top, leaving the other edges
  827.    on the same side as they started:  Twist top 30deg cl, flip,
  828.    twist top 30deg ccl, twist bottom 150deg cl, flip, twist bottom
  829.    30deg cl, twist top 120deg cl, flip, twist top 30deg ccl, twist
  830.    bottom 150deg cl, flip, twist bottom 30deg cl.  Cl and ccl are
  831.    defined looking directly at the face.  With this transformation
  832.    you can eventually get all the white edges on top.
  833.  
  834. 4. Check the parity of the edge sequence on each side.  If either is
  835.    wrong, you need to fix it.  Sorry -- I don't know how!  (See any
  836.    standard reference on combinatorics for an explanation of parity.)
  837.  
  838. 5. The following transformation cyclically permutes ccl all the top edges
  839.    but the right one and cl all the bottom edges but the left one.  Apply
  840.    the transformation in 3., and turn the whole cube 180deg.  Repeat.
  841.    This is a useful transformation, though not a cure-all.
  842.  
  843. 6. Varying the transformation in 3. with other twists will produce other
  844.    results.
  845.  
  846. 7. The following transformation changes a cube into a Comet and Star:
  847.    Flip to get Kite and Kite.  Twist top and bottom cl 90deg and flip to get
  848.    Barrel and Barrel.  Twist top cl 30 and bottom cl 60 and flip to get
  849.    Scallop and Scallop.  Twist top cl 60 and bottom cl 120 and flip to
  850.    get Comet and Star.  The virtue of the Star is that it contains only
  851.    corners, so that you can permute the corners without altering the edges.
  852.  
  853. 8. To reach a Lemon and Star instead, replace the final bottom cl 120 with
  854.    a bottom cl 60.  In both these transformation the Star is on the bottom.
  855.  
  856. 9. The following transformation cyclically permutes all but the bottom
  857.    left rear.  It sends the top left front to the bottom, and the bottom
  858.    left front to the top.  Go to Comet and Star.  Twist star cl 60.
  859.    Go to Lemon and Star -- you need not return all the way to the cube, but
  860.    do it if you're unsure of yourself by following 7 backwards.  Twist star
  861.    cl 60.  Return to cube by following 8 backwards.  With this transformation
  862.    you should be able to get all the white corners on top.
  863.  
  864. 10. Check the parity of the corner sequences on both sides.  If the bottom
  865.    parity is wrong, here's how to fix it:  Go to Lemon and Star.  The
  866.    colors on the Star will run WWGWWG.  Twist it 180 and return to cube.
  867.  
  868. 11. If the top parity is wrong, do the same thing, except that when you
  869.    go from Scallop and Scallop to Lemon and Star, twist the top and bottom
  870.    ccl instead of cl.  The colors on the Star should now run GGWGGW.
  871.  
  872. 12. Once the parity is right on both sides, the basic method is to
  873.    go to Comet and Star, twist the star 120 cl (it will be WGWGWG),
  874.    return to cube, twist one or both sides, go to Comet and Star,
  875.    undo the star twist, return to cube, undo the side twists.
  876.    With no side twists, this does nothing.  If you twist the top,
  877.    you will permute the top corners.  If you twist the bottom,
  878.    you will permute the bottom corners.  Eventually you will get
  879.    both the top and the bottom right.  Don't forget to undo the
  880.    side twists -- you need to have the edges in the right places.
  881.  
  882. Happy twisting....
  883. -- 
  884. Col. G. L. Sicherman
  885. gls@windmill.att.COM
  886.  
  887. ==> competition/games/think.and.jump.p <==
  888. THINK & JUMP:  FIRST THINK, THEN JUMP UNTIL YOU
  889.                ARE LEFT WITH ONE PEG!                      O - O   O - O
  890.                                                           / \ / \ / \ / \
  891.                                                          O---O---O---O---O
  892. BOARD DESCRIPTION:  To the right is a model of            \ / \ / \ / \ /
  893.                     the Think & Jump board.  The       O---O---O---O---O---O
  894.                     O's represent holes which         / \ / \ / \ / \ / \ / \
  895.                     contain pegs.                    O---O---O---O---O---O---O
  896.                                                       \ / \ / \ / \ / \ / \ /
  897.                                                        O---O---O---O---O---O
  898. DIRECTIONS:  To play this brain teaser, you begin         / \ / \ / \ / \
  899.              by removing the center peg.  Then,          O---O---O---O---O
  900.              moving any direction in the grid,            \ / \ / \ / \  /
  901.              jump over one peg at a time,                  O - O   O - O
  902.              removing the jumped peg - until only
  903.              one peg is left.  It's harder then it looks. 
  904.          But it's more fun than you can imagine.
  905.  
  906. SKILL CHART:
  907.  
  908.     10 pegs left - getting better
  909.      5 pegs left - true talent
  910.      1 peg  left - you're a genius
  911.  
  912. Manufactured by Pressman Toy Corporation, NY, NY.
  913.  
  914. ==> competition/games/think.and.jump.s <==
  915. Three-color the board in the obvious way.  The initial configuration has 12
  916. of each color, and each jump changes the parity of all three colors.  Thus,
  917. it is impossible to achieve any position where the colors do not have the
  918. same parity; in particular, (1,0,0).
  919.  
  920. If you remove the requirement that the initially-empty cell must be at the
  921. center, the game becomes solvable.  The demonstration is left as an exercise.
  922.  
  923. Karl Heuer   rutgers!harvard!ima!haddock!karl   karl@haddock.ima.isc.com
  924.  
  925.  
  926.  
  927.  
  928. Here is one way of reducing Think & Jump to two pegs.
  929.  
  930.  
  931. Long simplifies Balsley's scintillating snowflake solution:
  932.  
  933. 1  U-S           A - B   C - D
  934. 2  H-U          / \ / \ / \ / \
  935. 3  V-T         E---F---G---H---I
  936. 4  S-H          \ / \ / \ / \ /
  937. 5  D-M       J---K---L---M---N---O
  938. 6  F-S      / \ / \ / \ / \ / \ / \
  939. 7  Q-F     P---Q---R---S---T---U---V
  940. 8  A-L      \ / \ / \ / \ / \ / \ /
  941. 9  S-Q       W---X---Y---Z---a---b
  942. 10 P-R          / \ / \ / \ / \
  943. 11 Z-N         c---d---e---f---g
  944. 12 Y-K          \ / \ / \ / \ /
  945. 13 h-Y           h - i   j - k
  946. 14 k-Z
  947.  
  948. The board should now be in the snowflake pattern, i.e. look like
  949.  
  950.          o - *   * - o
  951.         / \ / \ / \ / \
  952.        *---o---*---o---*
  953.         \ / \ / \ / \ /
  954.      *---*---*---*---*---*
  955.     / \ / \ / \ / \ / \ / \
  956.    o---o---o---o---o---o---o
  957.     \ / \ / \ / \ / \ / \ /
  958.      *---*---*---*---*---*
  959.         / \ / \ / \ / \
  960.        *---o---*---o---*
  961.         \ / \ / \ / \ /
  962.          o - *   * - o
  963.  
  964. where o is empty and * is a peg.  The top and bottom can now be reduced
  965. to single pegs individually.  For example, we could continue
  966.  
  967. 15 g-T
  968. 16 Y-a
  969. 17 i-Z
  970. 18 T-e
  971. 19 j-Y
  972. 20 b-Z
  973. 21 c-R
  974. 22 Z-X
  975. 23 W-Y
  976. 24 R-e
  977.  
  978. which finishes the bottom.  The top can be done in a similar manner.
  979. -- 
  980. Chris Long
  981.  
  982. ==> competition/games/tictactoe.p <==
  983. In random tic-tac-toe, what is the probability that the first mover wins?
  984.  
  985. ==> competition/games/tictactoe.s <==
  986. Count cases.
  987.  
  988. First assume that the game goes on even after a win.  (Later figure
  989. out who won if each player gets a row of three.)  Then there are
  990. 9!/5!4! possible final boards, of which
  991.  
  992.     8*6!/2!4! - 2*6*4!/0!4! - 3*3*4!/0!4! - 1 = 98
  993.  
  994. have a row of three Xs.  The first term is 8 rows times (6 choose 2)
  995. ways to put down the remaining 2 Xs.  The second term is the number
  996. of ways X can have a diagonal row plus a horizontal or vertical row.
  997. The third term is the number of ways X can have a vertical and a
  998. horizontal row, and the 4th term is the number of ways X can have two
  999. diagonal rows.  All the two-row configurations must be subtracted to
  1000. avoid double-counting.
  1001.  
  1002. There are 8*6!/1!5! = 48 ways O can get a row.  There is no double-
  1003. counting problem since only 4 Os are on the final board.
  1004.  
  1005. There are 6*2*3!/2!1! = 36 ways that both players can have a
  1006. row.  (6 possible rows for X, each leaving 2 possible rows for O
  1007. and (3 choose 2) ways to arrange the remaining row.)  These
  1008. cases need further consideration.
  1009.  
  1010. There are 98 - 36 = 62 ways X can have a row but not O.
  1011.  
  1012. There are 48 - 36 = 12 ways O can have a row but not X.
  1013.  
  1014. There are 126 - 36 - 62 - 12 = 16 ways the game can be a tie.
  1015.  
  1016. Now consider the 36 configurations in which each player has a row.
  1017. Each such can be achieved in 5!4! = 2880 orders.  There are 3*4!4!
  1018. = 1728 ways that X's last move completes his row.  In these cases O
  1019. wins.  There are 2*3*3!3! = 216 ways that Xs fourth move completes
  1020. his row and Os row is already done in three moves.  In these cases O
  1021. also wins.  Altogether, O wins 1728 + 216 = 1944 out of 2880 times
  1022. in each of these 36 configurations.  X wins the other 936 out of
  1023. 2880.
  1024.  
  1025. Altogether, the probability of X winning is ( 62 + 36*(936/2880) ) / 126. 
  1026.  
  1027. win:   737 / 1260  ( 0.5849206... )
  1028. lose:  121 / 420   ( 0.2880952... )
  1029. draw:  8 / 63      ( 0.1269841... )
  1030.  
  1031. The computer output below agress with this analysis.
  1032.  
  1033. 1000000 games:  won 584865, lost 288240, tied 126895
  1034.  
  1035. Instead, how about just methodically having the program play every
  1036. possible game, tallying up who wins?
  1037.  
  1038. Wonderful idea, especially since there are only 9! ~ 1/3 million
  1039. possible games.  Of course some are identical because they end in
  1040. fewer than 8 moves.  It is clear that these should be counted
  1041. multiple times since they are more probable than games that go
  1042. longer.
  1043.  
  1044. The result:
  1045. 362880 games:  won 212256, lost 104544, tied 46080
  1046.  
  1047. #include <stdio.h>
  1048.  
  1049. int    board[9];
  1050. int    N, move, won, lost, tied;
  1051.  
  1052. int    perm[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
  1053.  
  1054. int    rows[8][3] = {
  1055.   { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 },
  1056.   { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 }
  1057. };
  1058.  
  1059.  
  1060. main()
  1061. {
  1062.   do {
  1063.     bzero((char *)board, sizeof board);
  1064.     for ( move=0; move<9; move++ ) {
  1065.       board[perm[move]] = (move&1) ? 4 : 1;
  1066.       if ( move >= 4 && over() )
  1067.     break;
  1068.     }
  1069.     if ( move == 9 )
  1070.       tied++;
  1071. #ifdef DEBUG
  1072.     printf("%1d%1d%1d\n%1d%1d%1d  w %d, l %d, t %d\n%1d%1d%1d\n\n",
  1073.        board[0], board[1], board[2],
  1074.        board[3], board[4], board[5], won, lost, tied,
  1075.        board[6], board[7], board[8]);
  1076. #endif
  1077.     N++;
  1078.   } while ( nextperm(perm, 9) );
  1079.  
  1080.   printf("%d games:  won %d, lost %d, tied %d\n", N, won, lost, tied);
  1081.   exit(0);
  1082. }
  1083.  
  1084. int    s;
  1085. int    *row;
  1086.  
  1087. over()
  1088. {
  1089.   for ( row=rows[0]; row<rows[8]; row+=3 ) {
  1090.     s = board[row[0]] + board[row[1]] + board[row[2]];
  1091.     if ( s == 3 )
  1092.       return ++won;
  1093.     if ( s == 12 )
  1094.       return ++lost;
  1095.   }
  1096.   return 0;
  1097. }
  1098.  
  1099. nextperm(c, n)
  1100. int    c[], n;
  1101. {
  1102.   int    i = n-2, j=n-1, t;
  1103.  
  1104.   while ( i >= 0 && c[i] >= c[i+1] )
  1105.     i--;
  1106.   if ( i < 0 )
  1107.     return 0;
  1108.   while ( c[j] <= c[i] )
  1109.     j--;
  1110.   t = c[i];  c[i] = c[j];  c[j] = t;
  1111.   i++;  j = n-1;
  1112.   while ( i < j ) {
  1113.     t = c[i];  c[i] = c[j];  c[j] = t;
  1114.     i++;  j--;
  1115.   }
  1116.   return 1;
  1117. }
  1118.  
  1119.  
  1120.  
  1121. ==> competition/tests/analogies/long.p <==
  1122. 1. Host : Guest :: Cynophobia : ?
  1123. 2. Mountain : Plain :: Acrocephalic : ?
  1124. 3. Lover : Believer :: Philofelist : ?
  1125. 4. 4 : 6 :: Bumblebee : ?
  1126. 5. 2 : 1 :: Major : ?
  1127. 6. 1 : 24 :: Group : ?
  1128. 7. 4 : 64 :: Crotchet : ?
  1129. 8. Last : First :: Grave : ?
  1130. 9. 7 : 9 :: Throne : ?
  1131. 10. Pride : Hatred :: Beelzebub : ?
  1132. 11. Dollar : Bond :: Grant : ?
  1133. 12. Ek : Sankh :: 1 : ?
  1134.  
  1135. ==> competition/tests/analogies/long.s <==
  1136. 1. Lyssophobia
  1137.  
  1138. Cynophobia is the fear of dogs; lyssophobia is the fear of rabies.  As
  1139. Rodney Adams pointed out, a word meaning the fear of fleas would be
  1140. even better, but I've been unable to locate such a word (although
  1141. surely one must exists).
  1142.  
  1143. 2. Homalocephalic
  1144.  
  1145. Acrocephalic is having a pointed head; homalocephalic is having a flat
  1146. head.  Rodney Adamas suggested "planoccipital", but on checking this
  1147. apparently refers to having a flat back of the skull, so he only gets
  1148. partial credit.
  1149.  
  1150. 3. Galeanthropist
  1151.  
  1152. A philofelist is a cat-lover (also commonly called an ailurophile);
  1153. a galeanthropist is a person who believes they are a cat.
  1154.  
  1155. 4. Blue Bird
  1156.  
  1157. A Camp Fire Girl who is 4 is in the Bumblebee Club; a Campfire Girl
  1158. who is 6 in the Blue Bird Club.  I should have had "4 or 5" instead
  1159. of "4" to remove ambiguity (e.g. Mark Brader suggested "triplane").
  1160.  
  1161. 5. Brigadier
  1162.  
  1163. A 2-star general in the army is a major general; a 1-star general
  1164. in the army is a brigadier general.
  1165.  
  1166. 6. Field Army
  1167.  
  1168. Army groupings; there are 24 "groups" in a "field army".
  1169.  
  1170. 7. Hemidemisemiquaver
  1171.  
  1172. A crotchet is a quarter-note; a hemidemisemiquaver is a sixty-fourth
  1173. note.  Rodney Adams and Mark Brader both got this.
  1174.  
  1175. 8. Prestissimo
  1176.  
  1177. In music prestissimo means extremely fast; grave means very slow to
  1178. the point of solemnity.  This question was poorly worded (I received
  1179. both "womb" and "cradle" as answers).
  1180.  
  1181. 9. Seraph
  1182.  
  1183. In the ninefold hierarchy of angels, a throne ranks 7th and a seraph
  1184. 9th (9th being most powerful).  Rodney Adams got this one.
  1185.  
  1186. 10. Sonneillon
  1187.  
  1188. In Father Sebastien Machaelis's (one of the more famous exorcists)
  1189. hierarchy of devils, Beelzebub is responsible for pride, Sonneillon
  1190. for hatred.
  1191.  
  1192. 11. Roosevelt
  1193.  
  1194. Grant is on the $50 bill; Roosevelt on the $50 savings bond.
  1195.  
  1196. 12. 10^14
  1197.  
  1198. Ek is 1 in Hindi; sankh is 10^14 (one hundred quadrillion).
  1199. -- 
  1200. Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
  1201.  
  1202. ==> competition/tests/analogies/pomfrit.p <==
  1203. 1. NATURAL: ARTIFICIAL :: ANKYLOSIS: ?
  1204. 2.  RESCUE FROM CHOKING ON FOOD, etc.: HEIMLICH :: ADJUSTING MIDDLE EAR PRESSURE: ?
  1205. 3. LYING ON OATH: PERJURY :: INFLUENCING A JURY: ?
  1206. 4. RECTANGLE: ELLIPSE :: MERCATOR: ?
  1207. 5. CLOSED: CLEISTOGAMY :: OPEN: ?
  1208. 6. FO'C'SLE: SYNCOPE :: TH'ARMY: ?
  1209. 7. FILMS: OSCAR :: MYSTERY NOVELS: ?
  1210. 8. QUANTITATIVE DATA: STATISTICS :: HUMAN SETTLEMENTS: ?
  1211. 9. 7: 19 : : SEPTIMAL: ?
  1212. 10. 3 TO 2: SESQUILATERAL :: 7 TO 5: ?
  1213. 11. SICILY: JAPAN :: MAFIA: ?
  1214. 12. CELEBRITIES: SYCOPHANTIC :: ANCESTORS: ?
  1215. 13. 95: 98 :: VENITE: ?
  1216. 14. MINCES: EYES :: PORKIES: ?
  1217. 15. POSTAGE STAMPS: PHILATELIST: MATCHBOX LABELS: ?
  1218. 16. MALE: FEMALE :: ARRENOTOKY: ?
  1219. 17 TAILOR: DYER :: SARTORIAL: ?
  1220. 18. HERMES: BACCHUS :: CADUCEUS: ?
  1221. 19. 2823: 5331 :: ELEPHANT: ?
  1222. 20. CENTRE OF GRAVITY: BARYCENTRIC :: ROTARY MOTION: ?
  1223. 21. CALIFORNIA: EUREKA :: NEW YOKK: ?
  1224. 22. MARRIAGE: DIGAMY :: COMING OF CHRIST: ?
  1225. 23. 6: 5 :: PARR: ?
  1226. 24. GROUP: INDIVIDUAL :: PHYLOGENESIS: ?
  1227. 25. 12: 11 :: EPSOM: ?
  1228.  
  1229. ==> competition/tests/analogies/pomfrit.s <==
  1230. 1. ARTHRODESIS
  1231. 2. VALSALVA
  1232. 3. EMBRACERY
  1233. 4. MOLLWEIDE
  1234. 5. CHASMOGAMY
  1235. 6. SYNAL(O)EPHA
  1236. 7. EDGAR
  1237. 8. EKISTICS
  1238. 9. DECENNOVAL
  1239. 10. SUPERBIQUINTAL
  1240. 11. YAKUZA
  1241. 12. FILIOPETISTIC
  1242. 13. CANTATE
  1243. 14. LIES
  1244. 15. PHILLUMENIST
  1245. 16. THELYTOKY
  1246. 17. TINCTORIAL
  1247. 18. THYRSUS
  1248. 19. ANTIQUARIAN
  1249. 20. TROCHILIC
  1250. 21. EXCELSIOR (mottos)
  1251. 22. PAROUSIA
  1252. 23. HOWARD (wives of Henry VIII)
  1253. 24. ONTOGENESIS
  1254. 25. GLAUBER (salts)
  1255.  
  1256.  
  1257.  
  1258. ==> competition/tests/analogies/quest.p <==
  1259. 1. Mother: Maternal :: Stepmother: ?
  1260. 2. Club: Axe :: Claviform: ?
  1261. 3. Cook Food: Pressure Cooker :: Kill Germs: ?
  1262. 4. Water: Air :: Hydraulic: ?
  1263. 5. Prediction: Dirac :: Proof: ?
  1264. 6. Raised: Sunken :: Cameo: ?
  1265. 7. 1: 14 :: Pound: ?
  1266. 8. Malay: Amok :: Eskimo Women: ?
  1267. 9. Sexual Intercourse: A Virgin :: Bearing Children: ?
  1268. 10. Jaundice, Vomiting, Hemorrhages: Syndrome :: Jaundice: ?
  1269. 11. Guitar: Cello :: Segovia: ?
  1270. 12. Bars: Leaves :: Eagle: ?
  1271. 13. Roll: Aileron :: Yaw: ?
  1272. 14. 100: Century :: 10,000: ?
  1273. 15. Surface: Figure :: Mobius: ?
  1274. 16. Logic: Philosophy :: To Know Without Conscious Reasoning: ?
  1275. 17. Alive: Parasite :: Dead: ?
  1276. 18. Sea: Land :: Strait: ?
  1277. 19. Moses: Fluvial :: Noah: ?
  1278. 20. Remnant: Whole :: Meteorite: ?
  1279. 21. Opossum, Kangaroo, Wombat: Marsupial :: Salmon, Sturgeon, Shad: ?
  1280. 22. Twain/Clemens: Allonym :: White House/President: ?
  1281. 23. Sculptor: Judoka :: Fine: ?
  1282. 24. Dependent: Independent :: Plankton: ?
  1283. 25. Matthew, Mark, Luke, John: Gospels :: Joshua-Malachi: ?
  1284. 26. Luminous Flux: Lumen :: Sound Absorption: ?
  1285. 27. 2: 3 :: He: ?
  1286. 28. Growth: Temperature :: Pituitary Gland: ?
  1287. 29. Spider: Arachnoidism :: Snake: ?
  1288. 30. Epigram: Anthology :: Foreign Passages: ?
  1289. 31. Pathogen: Thermometer :: Lethal Wave: ?
  1290. 32. Russia: Balalaika :: India: ?
  1291. 33. Involuntary: Sternutatory :: Voluntary: ?
  1292. 34. Unusual Hunger: Bulimia :: Hunger for the Unusual: ?
  1293. 35. Blind: Stag :: Tiresias: ?
  1294. 36. River: Fluvial :: Rain: ?
  1295. 37. Country: City :: Tariff: ?
  1296. 38. $/Dollar: Logogram :: 3, 5, 14, 20/Cent: ?
  1297. 39. Lung Capacity: Spirometer :: Arterial Pressure: ?
  1298. 40. Gold: Ductile :: Ceramic: ?
  1299. 41. 7: 8 :: Uranium: ?
  1300. 42. Judaism: Messiah :: Islam: ?
  1301. 43. Sight: Amaurosis :: Smell: ?
  1302. 44. Oceans: Cousteau :: Close Encounters of the Third Kind: ?
  1303. 45. Diamond/Kimberlite: Perimorph :: Fungus/Oak: ?
  1304. 46. Compulsion to Pull One's Hair: Trichotillomania :: 
  1305.     Imagine Oneself As a Beast: ?
  1306. 47. Cross: Neutralism :: Hexagram: ?
  1307. 48. Wing: Tail :: Fuselage: ?
  1308. 49. Bell: Loud :: Speak: ?
  1309. 50. Benevolence: Beg :: Philanthropist: ?
  1310. 51. 10: Decimal :: 20: ?
  1311. 52. Five-sided Polyhedron: Pentahedron :: ?
  1312.     Faces of Parallelepiped Bounded by a Square: ?
  1313. 53. Motor: Helicopter :: Airflow: ?
  1314. 54. Man: Ant :: Barter: ?
  1315. 55. United States: Soviet Union :: Cubism: ?
  1316. 56. State: Stipend :: Church: ?
  1317. 57. Motorcycle: Bicycle :: Motordrome: ?
  1318. 58. Transparent: Porous :: Obsidian: ?
  1319. 59. pi*r^2*h: 1/3*pi*r^2*h :: Cylinder: ?
  1320.  
  1321. ==> competition/tests/analogies/quest.s <==
  1322. Annotated solutions.
  1323.  
  1324. If there is more than one word that fits the analogy, we list the best
  1325. word first.  Goodness of fit considers many factors, such as parallel
  1326. spelling, pronunciation or etymology.  In general, a word that occurs
  1327. in Merriam-Webster's Third New International Dictionary is superior to
  1328. one that does not.  If we are unsure of the answer, we mark it with
  1329. a question mark.
  1330.  
  1331. Most of these answers are drawn from Herbert M. Baus, _The Master
  1332. Crossword Puzzle Dictionary_, Doubleday, New York, 1981.  The notation
  1333. in parentheses refers to the heading and subheading, if any, in Baus.
  1334.  
  1335. 1. Mother: Maternal :: Stepmother: Novercal (STEPMOTHER, pert.)
  1336. 2. Club: Axe :: Claviform: Dolabriform, Securiform (AXE, -shaped)
  1337.     "Claviform" is from Latin "clava" for "club"; "securiform" is from
  1338.     Latin "secura" for "axe"; "dolabriform" is from Latin "dolabra" for "to
  1339.     hit with an axe."  Thus "securiform" has the more parallel etymology.
  1340.     However, only "dolabriform" occurs in Merriam-Webster's Third New
  1341.     International Dictionary.
  1342. 3. Cook Food: Pressure Cooker :: Kill Germs: Autoclave (PRESSURE, cooker)
  1343. 4. Water: Air :: Hydraulic: Pneumatic (AIR, pert.)
  1344. 5. Prediction: Dirac :: Proof: Anderson (POSITRON, discoverer)
  1345. 6. Raised: Sunken :: Cameo: Intaglio (GEM, carved)
  1346. 7. 1: 14 :: Pound: Stone (ENGLAND, weight)
  1347. 8. Malay: Amok :: Eskimo Women: Piblokto (ESKIMO, hysteria)
  1348. 9. Sexual Intercourse: A Virgin :: Bearing Children: A Nullipara
  1349. 10. Jaundice, Vomiting, Hemorrhages: Syndrome :: Jaundice: Symptom (EVIDENCE)
  1350. 11. Guitar: Cello :: Segovia: Casals (SPAIN, cellist)
  1351. 12. Bars: Leaves :: Eagle: Stars (INSIGNIA)
  1352. 13. Roll: Aileron :: Yaw: Rudder (AIRCRAFT, part)
  1353. 14. 100: Century :: 10,000: Myriad, Banzai? (NUMBER)
  1354.      "Century" usually refers to one hundred years, while "myriad" refers
  1355.      to 10,000 things, but "century" can also mean 100 things.  "Banzai"
  1356.      is Japanese for 10,000 years.
  1357. 15. Surface: Figure :: Mobius: Klein
  1358. 16. Logic: Philosophy ::
  1359.     To Know Without Conscious Reasoning: Theosophy (MYSTICISM)
  1360.      There are many schools of philosophy that tout the possibility of
  1361.      knowledge without conscious reasoning (e.g., intuitionism).
  1362.      "Theosophy" is closest in form to the word "philosophy."
  1363. 17. Alive: Parasite :: Dead: Saprophyte (SCAVENGER)
  1364. 18. Sea: Land :: Strait: Isthmus (CONNECTION)
  1365. 19. Moses: Fluvial :: Noah: Diluvial (FLOOD, pert.)
  1366. 20. Remnant: Whole :: Meteorite: Meteoroid? (METEOR)
  1367.      A meteorite is the remains of a meteoroid after it has
  1368.      partially burned up in the atmosphere.  The original meteoroid
  1369.      may have come from an asteroid, comet, dust cloud, dark matter,
  1370.      supernova, interstellar collision or other sources as yet unknown.
  1371. 21. Opossum, Kangaroo, Wombat: Marsupial ::
  1372.     Salmon, Sturgeon, Shad: Andromous (SALMON)
  1373. 22. Twain/Clemens: Allonym :: White House/President: Metonym (FIGURE, of speech)
  1374. 23. Sculptor: Judoka :: Fine: Martial (SELF, -defense)
  1375. 24. Dependent: Independent :: Plankton: Nekton (ANIMAL, free-swimming)
  1376. 25. Matthew, Mark, Luke, John: Gospels ::
  1377.     Joshua-Malachi: Nebiim (HEBREW, bible books)
  1378. 26. Luminous Flux: Lumen :: Sound Absorption: Sabin (SOUND, absorption unit)
  1379. 27. 2: 3 :: He: Li (ELEMENT)
  1380. 28. Growth: Temperature :: Pituitary Gland: Hypothalamus (BRAIN, part)
  1381. 29. Spider: Arachnoidism :: Snake: Ophidism, Ophidiasis, Ophiotoxemia
  1382.      None of these words is in Webster's Third.
  1383. 30. Epigram: Anthology :: Foreign Passages: Chrestomathy, Delectus (COLLECTION)
  1384.      These words are equally good answers.
  1385. 31. Pathogen: Thermometer :: Lethal Wave: Dosimeter? (X-RAY, measurement)
  1386.      What does "lethal wave" refer to?  If it is radiation, then
  1387.      a dosimeter measures the dose, not the effect, as does a thermometer.
  1388. 32. Russia: Balalaika :: India: Sitar, Sarod (INDIA, musical instrument)
  1389.      Both are guitar-like instruments (lutes) native to India.
  1390. 33. Involuntary: Sternutatory :: Voluntary: Expectorant? (SPIT)
  1391.      A better word would be an agent that tends to cause snorting or
  1392.      exsufflation, which is the voluntary, rapid expulsion of air from
  1393.      the lungs.
  1394. 34. Unusual Hunger: Bulimia ::
  1395.     Hunger for the Unusual: Allotriophagy, Pica (HUNGER, unusual)
  1396.     These words are synonyms.
  1397. 35. Blind: Stag :: Tiresias: Actaeon (STAG, changed to)
  1398. 36. River: Fluvial :: Rain: Pluvial (RAIN, part.)
  1399. 37. Country: City :: Tariff: Octroi (TAX, kind)
  1400. 38. $/Dollar: Logogram :: 3, 5, 14, 20/Cent: Cryptogram (CODE)
  1401. 39. Lung Capacity: Spirometer ::
  1402.     Arterial Pressure: Sphygmomanometer (PULSE, measurer)
  1403. 40. Gold: Ductile :: Ceramic: Fictile (CLAY, made of)
  1404. 41. 7: 8 :: Uranium: Neptunium (ELEMENT, chemical)
  1405. 42. Judaism: Messiah :: Islam: Mahdi (MOHAMMEDAN, messiah)
  1406. 43. Sight: Amaurosis :: Smell: Anosmia, Anosphresia (SMELL, loss)
  1407.      These words are synonyms.
  1408. 44. Oceans: Cousteau :: Close Encounters of the Third Kind: Spielburg, Truffaut
  1409.      Steven Spielburg was the person most responsible for the movie;
  1410.      Francois Truffaut was a French person appearing in the movie.
  1411. 45. Diamond/Kimberlite: Perimorph ::
  1412.     Fungus/Oak: Endophyte, Endoparasite (PARASITE, plant)
  1413.      An endoparasite is parasitic, while an endophyte may not be.  Which
  1414.      answer is best depends upon the kind of fungus.
  1415. 46. Compulsion to Pull One's Hair: Trichotillomania :: 
  1416.     Imagine Oneself As a Beast: Zoanthropy, Lycanthropy
  1417.      Neither word is exactly right: "zoanthropy" means imagining oneself
  1418.      to be an animal, while "lycanthropy" means imagining oneself to be
  1419.      a wolf.
  1420. 47. Cross: Neutralism :: Hexagram: Zionism (ISRAEL, doctrine)
  1421. 48. Wing: Tail :: Fuselage: Empennage, Engines, Waist? (TAIL, kind)
  1422.      "Empennage" means the tail assemply of an aircraft, which is more a
  1423.      synonym for "tail" than "wing" is for "fuselage."  The four primary
  1424.      forces on an airplane are: lift from the wings, negative lift from
  1425.      the tail, drag from the fuselage, and thrust from the engines.  The
  1426.      narrow part at the end of the fuselage is called the "waist."
  1427. 49. Bell: Loud :: Speak: Hear, Stentorian?
  1428.      The Sanskrit root of "bell" means "he talks" or "he speaks"; the
  1429.      Sanskrit root of "loud" means "he hears".  A bell that makes a lot
  1430.      of noise is loud; a speaker who makes a lot of noise is stentorian.  
  1431. 50. Benevolence: Beg :: Philanthropist: Mendicant, Mendicate?
  1432.      If the analogy is attribute: attribute :: noun: noun, the answer
  1433.      is "mendicant";  if the analogy is noun: verb :: noun: verb the
  1434.      answer is "mendicate."
  1435. 51. 10: Decimal :: 20: Vigesimal (TWENTY, pert.)
  1436. 52. Five-sided Polyhedron: Pentahedron ::
  1437.     Faces of Parallelepiped Bounded by a Square: ?
  1438.      Does this mean a parallelepiped all of whose faces are bounded by
  1439.      a square (and what does "bounded" mean), or does it mean all six
  1440.      parallelograms that form the faces of a parallelepiped drawn in a
  1441.      plane inside of a square?
  1442. 53. Motor: Helicopter :: Airflow: Autogiro (HELICOPTER)
  1443. 54. Man: Ant :: Barter: Trophallaxis
  1444. 55. United States: Soviet Union :: Cubism: ? (ART, style)
  1445.      If the emphasis is on opposition and collapse, there were several
  1446.      movements that opposed Cubism and that died out (e.g., Purism,
  1447.      Suprematism, Constructivism).  If the emphasis is on freedom of
  1448.      perspective versus constraint, there were several movements that
  1449.      emphasized exact conformance with nature (e.g., Naturalism, Realism,
  1450.      Photo-Realism).  If the emphasis is on dominating the art
  1451.      scene, the only movement that was contemporary with Cubism and
  1452.      of the same popularity as Cubism was Surrealism.  A better answer
  1453.      would be an art movement named "Turkey-ism", since the Soviet Union
  1454.      offered to exchange missiles in Cuba for missiles in Turkey during
  1455.      the Cuban Missile Crisis.
  1456. 56. State: Stipend :: Church: Prebend (STIPEND)
  1457. 57. Motorcycle: Bicycle :: Motordrome: Velodrome (CYCLE, track)
  1458. 58. Transparent: Porous :: Obsidian: Pumice (GLASS, volcanic)
  1459. 59. pi*r^2*h: 1/3*pi*r^2*h :: Cylinder: Cone
  1460.  
  1461. ==> competition/tests/math/putnam/putnam.1967.p <==
  1462.  
  1463. In article <5840002@hpesoc1.HP.COM>, nicholso@hpesoc1.HP.COM (Ron Nicholson) writes:
  1464. > Say that we have a hallway with n lockers, numbered from sequentialy
  1465. > from 1 to n.  The lockers have two possible states, open and closed. 
  1466. > Initially all the lockers are closed.  The first kid who walks down the
  1467. > hallway flips every locker to the opposite state, that is, opens them
  1468. > all.  The second kid flips the first locker door and every other locker
  1469. > door to the opposite state, that is, closes them.  The third kid flips
  1470. > every third door, opening some, closing others.  The forth kid does every
  1471. > fourth door, etc.
  1472. > 
  1473. > After n kid have passed down the hallway, which lockers are open, and
  1474. > which are closed?
  1475.  
  1476. B4.  (a) Kids run down a row of lockers, flipping doors (closed doors
  1477. are opened and opened doors are closed).  The nth boy flips every nth
  1478. lockers' door.  If all the doors start out closed, which lockers will
  1479. remain closed after infinitely many kids?
  1480.  
  1481. ==> competition/tests/math/putnam/putnam.1967.s <==
  1482. B4.  (a) Only lockers whose numbers have an odd number of factors will remain
  1483. closed, which are the squares.
  1484.